package algorithm.recurrence;

import java.util.Random;

import algorithm.sort.SortSYT;

public class FindMaxSubArraySYT {
	
	public SubArrayResult FindMaxCrossingSubArray(int[] a, int low, int mid, int high){
		int leftSum = Integer.MIN_VALUE;
		int leftIndex = mid;
		int sum = 0;
		for(int i = mid; i >= low; i--){
			sum += a[i];
			if(sum > leftSum){
				leftSum = sum;
				leftIndex = i;
			}
		}
		
		int rightSum = Integer.MIN_VALUE;
		int rightIndex = mid + 1;
		sum = 0;
		for(int i = mid + 1; i <= high; i++){
			sum += a[i];
			if(sum > rightSum){
				rightSum = sum;
				rightIndex = i;
			}
		}
		return new SubArrayResult(leftIndex,rightIndex,leftSum + rightSum);
	}
	
	public SubArrayResult FindMaxSubArray(int[] a,int low,int high){
		if(low == high){
			return new SubArrayResult(low,high,a[low]);
		}
		
		int mid = (high + low) / 2;
		SubArrayResult lowResult = FindMaxSubArray(a,low,mid);
		SubArrayResult highResult = FindMaxSubArray(a,mid + 1,high);
		SubArrayResult crossResult = FindMaxCrossingSubArray(a,low,mid,high);
		
		if(lowResult.compare(highResult) && lowResult.compare(crossResult)){
			return lowResult;
		}else if(highResult.compare(lowResult) && highResult.compare(crossResult)){
			return highResult;
		}else{
			return crossResult;
		}
		
	}
	
	public int[] transformArr(int[] a){
		int[] result = new int[a.length - 1];
		for(int i = 0; i < a.length - 1; i ++){
			result[i] = a[i + 1] - a[i];
		}
		return result;
	}
	
	public void print(int[] a,SubArrayResult result){
		System.out.println("\n" + a[result.getLeftIndex()] + " " + a[result.getRightIndex() + 1]);
	}
	
	public void printArr(int[] a){
		String s = "\n";
		for(int i = 0; i < a.length; i++){
			s  = s + " " + a[i];
		}
		System.out.println(s);
	}
	
	private class SubArrayResult{
		private int leftIndex;
		private int rightIndex;
		private int sum;
		
		public SubArrayResult(int leftIndex, int rightIndex, int sum){
			this.leftIndex = leftIndex;
			this.rightIndex = rightIndex;
			this.sum = sum;
		}

		public int getLeftIndex() {
			return leftIndex;
		}

		public void setLeftIndex(int leftIndex) {
			this.leftIndex = leftIndex;
		}

		public int getRightIndex() {
			return rightIndex;
		}

		public void setRightIndex(int rightIndex) {
			this.rightIndex = rightIndex;
		}

		public int getSum() {
			return sum;
		}

		public void setSum(int sum) {
			this.sum = sum;
		}
		
		public boolean compare(SubArrayResult other) {
			return this.sum >= other.getSum();
		}
		
		public void print() {
			String s = "\nleftIndex:" + leftIndex + " rightIndex:" + rightIndex + " sum:" + sum;
			System.out.println(s);
		}
		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		FindMaxSubArraySYT find = new FindMaxSubArraySYT();
		
		int[] a = new int[1000];
		Random random = new Random();
		for(int i = 0; i< 1000; i++){
			a[i] = random.nextInt(1000);
		}
	//	find.printArr(a);
		int[] transformA = find.transformArr(a);
	//	find.printArr(transformA);
	//	find.printArr(a);
		SubArrayResult subArrayResult = find.FindMaxSubArray(transformA, 0, transformA.length - 1);
		subArrayResult.print();
		find.print(a, subArrayResult);
	}
}
